Skip to main content

Hash table

Checking for existence​

Two sum​

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let dic = new Map();
  for (let i = 0; i < nums.length; i++) {
    let num = nums[i];
    let complement = target - num;
    if (dic.has(complement)) {
      return [i, dic.get(complement)];
    }

    dic.set(num, i);
  }

  return [-1, -1];
};

First letter to appear twice​

/**
 * @param {string} s
 * @return {character}
 */
var repeatedCharacter = function (s) {
  let seen = new Set();
  for (const c of s) {
    if (seen.has(c)) {
      return c;
    }

    seen.add(c);
  }

  return " ";
};

Missing number in arr​

/**
 * @param {number[]} nums
 * @return {number}
 */
var missingNumber = function (nums) {
  let set = new Set();

  for (const num of nums) {
    set.add(num);
  }

  for (let i = 0; i <= nums.length; i++) {
    if (!set.has(i)) {
      return i;
    }
  }
};

Counting​

JavaScript

let fn = (arr, k) => {
  let counts = new Map();
  counts.set(0, 1);
  let ans = 0,
    curr = 0;

  for (const num of arr) {
    // do logic to change curr
    ans += counts.get(curr - k) || 0;
    counts.set(curr, (counts.get(curr) || 0) + 1);
  }

  return ans;
};

Find the length of the longest substring that contains at most k distinct characters​

For example, given s = "eceba" and k = 2, return 3. The longest substring with at most 2 distinct characters is "ece".

let findLongestSubstring = (s, k) => {
  let counts = new Map();
  let left = 0;
  let ans = 0;

  for (let right = 0; right < s.length; right++) {
    counts.set(s[right], (counts.get(s[right]) || 0) + 1);
    while (counts.size > k) {
      counts.set(s[left], counts.get(s[left]) - 1);
      if (counts.get(s[left]) == 0) {
        counts.delete(s[left]);
      }
      left++;
    }

    ans = Math.max(ans, right - left + 1);
  }

  return ans;
};

Intersection of multiple arrays​

Input: nums = [[3,1,2,4,5],[1,2,3,4],[3,4,5,6]]
Output: [3,4]
Explanation:
The only integers present in each of nums[0] = [3,1,2,4,5], nums[1] = [1,2,3,4], and nums[2] = [3,4,5,6] are 3 and 4, so we return [3,4].

/**
 * @param {number[][]} nums
 * @return {number[]}
 */
var intersection = function (nums) {
  let counts = new Map();
  for (const arr of nums) {
    for (const x of arr) {
      counts.set(x, (counts.get(x) || 0) + 1);
    }
  }

  let n = nums.length;
  let ans = [];
  for (const [key, val] of counts) {
    if (val == n) {
      ans.push(key);
    }
  }

  ans.sort((a, b) => a - b);
  return ans;
};

Subarray Sum Equals K​

Input: nums = [1,1,1], k = 2
Output: 2

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var subarraySum = function (nums, k) {
  let count = new Map();
  count.set(0, 1);
  let ans = 0;
  let curr = 0;

  for (const num of nums) {
    curr += num;
    ans += count.get(curr - k) || 0;
    count.set(curr, (count.get(curr) || 0) + 1);
  }

  return ans;
};

Find Players with zero or one losses​

Input: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
Output: [[1,2,10],[4,5,7,8]]
Explanation:
Players 1, 2, and 10 have not lost any matches.
Players 4, 5, 7, and 8 each have lost one match.
Players 3, 6, and 9 each have lost two matches.
Thus, answer[0] = [1,2,10] and answer[1] = [4,5,7,8].

var findWinners = function (matches) {
  const loserMap = new Map();

  for (const [winner, loser] of matches) {
    if (!loserMap.has(winner)) {
      loserMap.set(winner, 0);
    }

    loserMap.set(loser, (loserMap.get(loser) || 0) + 1);
  }

  const zero = [];
  const one = [];

  for (const [player, count] of loserMap) {
    if (count === 0) {
      zero.push(player);
    } else if (count === 1) {
      one.push(player);
    }
  }

  zero.sort((a, b) => a - b);
  one.sort((a, b) => a - b);

  return [zero, one];
};

Other​

Group Anagrams​

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

/**
 * @param {string[]} strs
 * @return {string[][]}
 */
var groupAnagrams = function (strs) {
  if (strs.length <= 1) return [strs];
  const map = new Map();

  for (const str of strs) {
    const key = str.split("").sort().join("");
    const group = map.get(key) || [];
    group.push(str);
    map.set(key, group);
  }

  return Array.from(map.values());
};

Longest Substring Without Repeating Characters​

Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function (s) {
  const map = new Map();
  let max = 0;
  let start = 0;

  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i]) && map.get(s[i]) >= start) {
      start = map.get(s[i]) + 1;
    }

    map.set(s[i], i);
    max = Math.max(max, i - start + 1);
  }

  return max;
};